package io.github.consoles.dsa;

import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * Created by yiihua-013 on 17/2/6.
 * <p>
 * 数组实现自动扩容的队列
 */
public class ArrayQueue<Item> implements Iterable<Item> {

    private Item[] arr;
    private int    size;

    private static final int DEFAULT_CAPACITY = 2;

    public ArrayQueue() {
        this(DEFAULT_CAPACITY);
    }

    /**
     * 得到队列q的副本
     * http://www.cnblogs.com/songdechiu/p/6522526.html
     *
     * @param q
     */
    public ArrayQueue(ArrayQueue<Item> q) {
//        ArrayQueue<Item> tmp  = new ArrayQueue<Item>();
//        int              size = q.size();
//        // 一个队列进行n次出队列马上进行入队列操作,刚好转了个圈,顺序和原来队列相同
//        for (int i = 0; i < size; i++) {
//            Item item = q.dequeue();
//            q.enqueue(item);
//            tmp.enqueue(item);
//        }
//        // 修改数据实体指向新的队列(如果是链表实现的需要修改first,last和size)
//        this.arr = tmp.arr;
//        this.size = tmp.size;

        arr = (Item[]) new Object[DEFAULT_CAPACITY];
        size = 0;
        for (Item item : q) {
            this.enqueue(item);
        }
    }

    public ArrayQueue(int cap) {
        arr = (Item[]) new Object[cap];
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public int size() {
        return size;
    }

    public void enqueue(Item item) {
        if (arr.length == size) resize(2 * size);
        arr[size++] = item;
    }

    public Item dequeue() {
        if (isEmpty()) throw new RuntimeException("Queue is Empty");
        Item item = arr[0];
        // 每次进行出队列操作都需要移动几乎所有元素,效率低下
        for (int i = 0; i < arr.length - 1; i++) {
            arr[i] = arr[i + 1];
        }
        size--;
        return item;
    }

    /**
     * 队列扩容
     */
    private void resize(int cap) {
        Item[] temp = (Item[]) new Object[cap];
        for (int i = 0; i < size; i++) {
            temp[i] = arr[i];
        }
        arr = temp;
    }

    private class ArrayQueueIterator implements Iterator<Item> {

        private int index = 0;

        @Override
        public boolean hasNext() {
            return index < size;
        }

        @Override
        public Item next() {
            if (!hasNext()) throw new NoSuchElementException();
            return arr[index++];
        }
    }

    @Override
    public Iterator<Item> iterator() {
        return new ArrayQueueIterator();
    }
}
